Prof. Caprile

Anno Accademico 2001/2002

Il corso mira ad introdurre gli elementi essenziali della teoria dei codici a correzione di errore - ovvero dei metodi coi quali viene modernamente affrontato il problema della trasmissione di messaggi digitali in presenza di disturbi. Il punto di vista ed il linguaggio adottati sono quelli della teoria algebrica dei codici, ma congruo spazio viene altresi` riservato ai concetti ed ai risultati fondamentali dell'approccio statistico.

L'impostazione del corso e` prevalentemente teorica. Gli esercizi proposti sono volti sia a consolidare la familiarita` con i concetti, sia ad integrare le nozioni teoriche esposte nel corso delle lezioni. Ove opportuno, enfasi viene posta ad evidenziare gli aspetti algoritmici dei metodi introdotti.

1) Generalita`: il problema della trasmissione di messaggi (digitali) in presenza di disturbi;

2) Nozioni di distanza minima e di equivalenza fra codici. Limite di Hamming e codici perfetti;

3) Schemi probabilistici: incertezza associata ed entropia; proprieta`;

4) Sorgenti (a memoria zero) ed associati schemi di codifica. Codici istantanei;

5) Teorema di codifica in assenza di rumore. Esistenza di codici compatti. Algoritmo di Huffman;

6) Canali di trasmissione; capacita`;

7) Codifica in presenza di rumore;

8) Codici lineari: loro struttura e proprieta`. Codifica e decodifica: sindrome;

9) Codici di Hamming e di Golay;

10) Codici BCH: loro costruzione e proprieta`. Esempi;

11) Codici ciclici e loro caratterizzazione algebrica. Polinomio generatore; matrice generatrice; polinomio di controllo e matrice di controllo;

12) Codici di Reed-Muller; matrici e trasformata di Hadamard; decodifica.

- L. Berardi, Algebra e teoria dei codici correttori, Franco Angeli, 1994.

- R. Hill, A First Course in Coding Theory, Clarendon Press, 1986.

- A. I. Khinchin, Mathematical Foundations of Information Theory, Dover Publications, 1957.

- J. H. van Lint, Introduction to Coding Theory, Springer, 1998.

- D. Welsh, Codes and Cryptography, Oxford University Press, 1988.